/*
https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
 */
public class Solution287 {
    public int findDuplicate(int[] nums) {
        int slow=nums[0];
        int fast=nums[0];
        do{
            slow=nums[slow];
            fast=nums[fast];
            fast=nums[fast];
        }while (fast!=slow);
        int p=nums[0];
        while (p!=slow){
            slow=nums[slow];
            p=nums[p];
        }
        return p;
    }

    public static void main(String[] args) {
        System.out.println(new Solution287().findDuplicate(new int[]{1,3,4,2,2}));
    }
}
